package index;

import algebra.OrderingDescription;
import utils.exception.OrderingDescriptionException;
import entities.ConceptAssertion;


public class TreeUtils {
  private static boolean new_depth;

  private static IndexTreeNode single_rotate(IndexTreeNode tree, int dir) {
    int not_dir = dir == 0 ? 1 : 0;
    IndexTreeNode save = tree.link.get(dir);
    tree.link.set(dir, save.link.get(not_dir));
    save.link.set(not_dir, tree);
    return save;
  }

  private static IndexTreeNode double_rotate(IndexTreeNode tree, int dir) {
    int not_dir = dir == 0 ? 1 : 0;
    IndexTreeNode save = tree.link.get(dir).link.get(not_dir);
    tree.link.get(dir).link.set(not_dir, save.link.get(dir));
    save.link.set(dir, tree.link.get(dir));
    tree.link.set(dir, save);
    save = tree.link.get(dir);
    tree.link.set(dir, save.link.get(not_dir));
    save.link.set(not_dir, tree);
    return save;
  }

  private static void fix_balance_factors(IndexTreeNode tree, int dir) {
    int not_dir = dir == 0 ? 1 : 0;
    
    if (tree.link.get(dir).link.get(not_dir).balance == dir) {
      tree.balance = 2;
      tree.link.get(dir).balance = not_dir;
    }
    else if (tree.link.get(dir).link.get(not_dir).balance == not_dir) {
      tree.balance = dir;
      tree.link.get(dir).balance = 2;
    }
    else {
      tree.balance = tree.link.get(dir).balance = 2;
    }
    tree.link.get(dir).link.get(not_dir).balance = 2;
  }

  private static IndexTreeNode rebalance_insert(IndexTreeNode tree, int dir) {

    int not_dir = dir == 0 ? 1 : 0;
    if (tree.balance == dir) {
      if (tree.link.get(dir).balance == dir) {
        tree.link.get(dir).balance = 2;
        tree.balance = 2;
        tree = single_rotate(tree, dir);
      }
      else {
        fix_balance_factors(tree, dir);
        tree = double_rotate(tree, dir);
      }
      new_depth = false;
    }
    else if (tree.balance == not_dir) {
      tree.balance = 2;
      new_depth = false;
    }
    else {
      tree.balance = dir;
    }
    return tree;
  }

  private static IndexTreeNode rebalance_remove(IndexTreeNode tree, int dir) {

    int not_dir = dir == 0 ? 1 : 0;

    if (tree.balance == dir) {
      tree.balance = 2;
    }
    else if (tree.balance == not_dir) {
      if (tree.link.get(not_dir).balance == not_dir) {
        tree.link.get(not_dir).balance = 2;
        tree.balance = 2;
        tree = single_rotate(tree, not_dir);
      }
      else if (tree.link.get(not_dir).balance == 2) {
        tree.link.get(not_dir).balance = dir;
        tree = single_rotate(tree, not_dir);
      }
      else {
        fix_balance_factors(tree, not_dir);
        tree = double_rotate(tree, not_dir);
      }
      new_depth = false;
    }
    else {
      tree.balance = not_dir;
      new_depth = false;
    }
    return tree;
  }

  private static IndexTreeNode insert_r(IndexTreeNode tree, OrderingDescription od, ConceptAssertion ca) throws OrderingDescriptionException {
    if (tree == null) {
      tree = new IndexTreeNode (ca);
      new_depth = true;
    }

    else {
      //int dir = data.compareTo(tree.data) > 0 ? 1 : 0;
      int dir = od.compare(ca, tree.getNodeAssertion()) > 0 ? 1 : 0;
      tree.link.set(dir, insert(tree.link.get(dir), od, ca));
      if (new_depth) {
        tree = rebalance_insert(tree, dir);
      }
    }
    return tree;
  }

  private static IndexTreeNode remove_r(IndexTreeNode tree, OrderingDescription od, ConceptAssertion data) throws OrderingDescriptionException {
    if (tree == null) {
      new_depth = false;
    }
    else if (od.compare(data, tree.getNodeAssertion()) == 0) {
      if (tree.link.get(0) != null && tree.link.get(1) != null) {
        IndexTreeNode heir = tree.link.get(0);
        while (heir.link.get(1) != null) {
          heir = heir.link.get(1);
        }
        tree.data = heir.data;
        tree.link.set(0, remove_r(tree.link.get(0), od, tree.getNodeAssertion()));
        if (new_depth) {
          tree = rebalance_remove(tree, 0);
        }
      }
      else {
        //AVLNode<T> save = tree;
        tree = tree.link.get(tree.link.get(0) == null ? 1 : 0);
        new_depth = true;
      }
    }
    else {
      int dir = od.compare(data, tree.getNodeAssertion()) > 0 ? 1 : 0;
      //int dir = data.compareTo(tree.data) > 0 ? 1 : 0;
      tree.link.set(dir, remove_r(tree.link.get(dir), od, data));
      if (new_depth) {
        tree = rebalance_remove(tree, dir);
      }
    }
    return tree;
  }

  public static IndexTreeNode insert(IndexTreeNode tree, OrderingDescription od, ConceptAssertion ca) throws OrderingDescriptionException {
    new_depth = false;
    return insert_r(tree, od, ca);
  }

  public static IndexTreeNode remove(IndexTreeNode tree, OrderingDescription od, ConceptAssertion data) throws OrderingDescriptionException {
    new_depth = false;
    return remove_r(tree, od, data);
  }

  public static void structure(IndexTreeNode tree, int level) {
    int i;
    if (tree == null) {
      for (i = 0; i < level; i++) {
        System.out.print("\t");
      }
      System.out.println();
      return;
    }
    structure(tree.link.get(1), level + 1);
    for (i = 0; i < level; i++) {
      System.out.print("\t");
    }
    System.out.println(tree.data + "(" + tree.balance + ")");
    structure(tree.link.get(0), level + 1);
  }
  
}

